package Leetcode;

/**
 * 假设你正在爬楼梯，需要 n 阶你才能到达楼顶。
 * 每次你可以爬 1 或 2 个台阶，你有多少种不同的方法可以爬到楼顶呢
 *
 * @Author piper
 * @Date 2019/10/24 10:25 上午
 */
public class 力扣70_爬楼梯 {

    /**
     * 官网：1 暴力法
     * 把所有可能爬的阶数进行组合，也就是 1 和 2，
     * 而在每一步中我们都会继续调用 climbStairs 这个函数模拟爬 11 阶和 22 阶的情形，并返回两个函数的返回值之和。
     * <p>
     * 每次可以爬1或2，爬1过后面临的选择1、2，爬2之后面临爬1、2，可以看出这是一个递归
     * 这样想，一个人正在爬楼梯，第一步要么一步要么两步
     * 不管后面如何选择，第一步肯定是1，2 后面怎么选择我就不关心了
     * 我只需要递归（后面面临的 当作一个新的楼梯处理）走一步之后剩下的楼梯，和走两步之后剩下的楼梯
     */
    static int climb_stairs(int n) {
        return climbStairs(0, n);
    }

    static int climbStairs(int i, int n) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        return climbStairs(i + 1, n) + climbStairs(i + 2, n);
    }

    /**
     * 官网：2 记忆化递归
     * 在上一种方法中，我们计算每一步的结果时出现了冗余。
     * 另一种思路是，我们可以把每一步的结果存储在 memomemo 数组之中，
     * 每当函数再次被调用，我们就直接从 memomemo 数组返回结果。
     */
    static int climb_stairs1(int n) {
        int[] memo = new int[n + 1];
        return climbStairs1(0, n, memo);
    }

    static int climbStairs1(int i, int n, int[] memo) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        if (memo[i] > 0) {
            return memo[i];
        }
        return memo[i] = climbStairs1(i + 1, n, memo) + climbStairs1(i + 2, n, memo);
    }

    /**
     * 动态规划 1
     * 经过观察 每层的走法 = 前两层的走法之和
     * <p>
     * 我们用 f(x)f(x) 表示爬到第 xx 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子：
     * 它意味着爬到第 xx 级台阶的方案数是爬到第 x - 1x−1 级台阶的方案数和爬到第 x - 2x−2 级台阶的方案数的和。很好理解，
     * 因为每次只能爬 11 级或 22 级，所以 f(x)f(x) 只能从 f(x - 1)f(x−1) 和 f(x - 2)f(x−2) 转移过来，
     * 而这里要统计方案总数，我们就需要对这两项的贡献求和。
     * f(x)=f(x−1)+f(x−2)
     * <p>
     * 1 1
     * 2 2
     * 3 3
     * 4 5
     * 5 8
     * 6 13
     * 7 21
     * 8 34
     */
    static int climb_stairs2(int n) {
        if (n < 3) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i < n + 1; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    /**
     * 动态规划 2  对上边动态规划移除辅助数组
     */
    static int climb_stairs3(int n) {
        int p, q = 0, r = 1;
        for (int i = 1; i < n; i++) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }


    public static void main(String[] args) {
        System.out.println(climb_stairs3(5));
        System.out.println(climb_stairs3(6));
        System.out.println(climb_stairs3(7));
        System.out.println(climb_stairs3(8));
        System.out.println(climb_stairs3(9));
    }

}
